1
线性结构概论:数据项的相对位置与逻辑特征
AI028 Lesson 3
00:00

线性结构的本质:逻辑上的“排队”

线性数据结构(Linear Data Structure)并非指数据在内存中必须像士兵排队一样整齐。其本质特征在于数据项之间存在唯一的相对位置关系。在这种逻辑模型中,除了首尾元素,每个项都有一个明确的“前驱”和“后继”。

Diagram 3-18: 逻辑线性 vs 物理离散 54 0x1A4 26 0x8C1 93 0x2F0 17 0x4B2 即使物理位置随机分布,通过“逻辑线”即可维持顺序

ADT 的封装力量

抽象数据类型 (ADT) 是我们对这种逻辑关系的严谨定义。它将“做什么”(操作定义)与“怎么做”(具体存储)彻底解耦。就像一列火车:无论火车是在直道还是弯道(物理位置改变),车厢之间的相对顺序(逻辑特征)始终不变。

算法复杂度初步感知
理解线性结构不只是看结构,更要看效率。同样的逻辑遍历,使用 $O(\log n)$ 的对数阶逻辑与 $O(n^3)$ 的三层嵌套循环,在处理海量数据时有着天壤之别。